//第一种解法：
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
       //第一种方法使用m+n的空间解决，遍历原数组，记录下来需要变成0的行和列，然后遍历原数组去进行变化即可
       int m = matrix.size();
       int n = matrix[0].size();
       vector<int> row(m,1);//标记哪些行需要设置为0
       vector<int> col(n,1);//标记哪些列需要设置为0
       for(int i = 0;i<m;i++)
       {
        for(int j = 0;j<n;j++)
        {
            if(matrix[i][j] == 0)
            {
                row[i] = col[j] = 0;
            }
        }
       }
       //设置为0
       for(int i = 0;i<m;i++)
       {
        for(int j = 0;j<n;j++)
        {
            if(row[i] == 0||col[j] == 0)
            {
                matrix[i][j] = 0;
            }
        }
       }
       return;
    }
};
//第二种方法
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        //第二种解法将原数组的第一行和第一列当作额外的空间
        //首先需要标记一下第一行或者第一列是否出现了0
        bool bool_row = false;
        bool bool_col = false;
        for(int j = 0;j<matrix[0].size();j++)
        {
            if(matrix[0][j] == 0)
            {
                bool_col = true;
                break;
            }
        }//处理第一行
        for(int j = 0;j<matrix.size();j++)
        {
            if(matrix[j][0] == 0)
            {
                bool_row = true;
                break;
            }
        }//处理第一列
        //然后就是遍历原数组,将第一行和第一列当作额外的空间了
        //行来标记列，列来标记行
        for(int i = 1;i<matrix.size();i++)
        {
            for(int j = 1 ;j<matrix[i].size();j++)
            {
                if(matrix[i][j] == 0)
                {
                    matrix[0][j] = matrix[i][0] = 0;
                }
            }
        }
        //通过标记数组来进行设置为0
        for(int i = 1;i<matrix.size();i++)
        {
            for(int j = 1;j<matrix[i].size();j++)
            {
                if(matrix[0][j]==0||matrix[i][0]==0)
                {
                    matrix[i][j] = 0;
                }
            }
        }
        //处理第一行
        if(bool_col)
        {
            for(int j = 0;j<matrix[0].size();j++)
            {
                matrix[0][j] = 0;
            }
        }
        //处理第一列
        if(bool_row)
        {
            for(int j = 0;j<matrix.size();j++)
            {
                matrix[j][0] = 0;
            }
        }
        return;
    }
};